package bag_01;

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main
{
	private static BufferedInputStream in = new BufferedInputStream(System.in);
	private static int[] v;
	private static int[] w;
	private static int[] dp;
	
	public static void main(String[] args) throws IOException
	{
		while(true)
			next();
	}
	
	private static void next() throws IOException
	{
		int s = readInt();
		int m = readInt();
		
		v = new int[s+1];
		w = new int[s+1];
		for(int i=1; i<=s; i++)
		{
			w[i] = readInt();
			v[i] = readInt();
		}
		
		dp = new int[m+1];
		
		for(int i=1; i<=s; i++)
		{
			for(int j=m; j>=w[i]; j--)
			{
				dp[j] = max(dp[j-w[i]] + v[i], dp[j]);
			}
		}
			
		System.out.println(dp[m]);
		
		System.out.println(Arrays.toString(dp));
	}

	private static int max(int i, int j)
	{
		return i>j?i:j;
	}

	private static int readInt() throws IOException
	{
		int i,sum=0;
		
		while(((i=in.read())&48) != 48 || i>57);
		
		for(;(i&56) == 48 || (i&62) == 56; i=in.read())
			sum = sum*10 + (i&15);
		
		return sum;
	}
}
